#include "stdafx.h"
#include "CLinearSort.h"
#include "include/tool.h"

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <gtest/gtest.h>

typedef unsigned __int32  uint32_t;

static void radix(int byte, const unsigned N, const uint32_t *source, uint32_t *dest)
{
  unsigned count[256];
  unsigned index[256];
  memset(count, 0, sizeof (count));

  for(unsigned i=0; i<N; ++i)
    count[((source[i])>>(byte*8))&0xff]++;

  index[0]=0;
  for(unsigned i=1; i<256; ++i)
    index[i] = index[i-1] + count[i-1];

  for(unsigned i=0; i<N; ++i)
    dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
}

void radixsort(uint32_t *source, const unsigned N)
{
  uint32_t *temp = new uint32_t[N];
  radix(0, N, source, temp);
  radix(1, N, temp, source);
  radix(2, N, source, temp);
  radix(3, N, temp, source);
  delete [] temp;
}

static void make_random(uint32_t *data, const unsigned N)
{
  for (unsigned i=0; i<N; ++i)
    data[i] = rand() | (rand()<<16);
}

static void check_order(const uint32_t *data, unsigned N)
{
  for(--N ; N > 0; --N, ++data)
    assert(data[0] <= data[1]);
}

template<typename T>
void count_sort(T A[], int size, T B[], int k) {
    T C[k+1] = new T[k+1];
    for (int i = 0; i < k+1; ++i) {
        C[i] = 0;
    }

    for (int i = 0; i < size; ++i) {
        C[A[i]]++;
    }
    for (int i = 1; i < k+1; ++i) {
        C[i] += C[i-1];
    }

    for (int i = size-1; i >=0; --i) {
        B[C[A[i]]] = A[i];
        C[A[i]]--;
    }
    delete [] C;
}

CLinearSort::CLinearSort()
{
    //ctor
}

CLinearSort::~CLinearSort()
{
    //dtor
}

int CLinearSort::run(void) {
    uint32_t data[100];
    make_random(data, 100);
    radixsort(data, 100);
    check_order(data, 100);
    print_array(data, 100);

    return 0;
}

TEST(CLinearSort, run)
{
	CLinearSort().run();
}

